#include<iostream>//单源点最短路径
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int INF=1e9;
struct enode
{
    int vex,wgt;
    enode *next;
}a[1000010],*adj[1000010],*s;
struct node
{
    int no,dis;
    bool operator<(const node &y)const{
        return dis>y.dis;
    }
}d[1000010];
priority_queue<node>q;
bool vis[1000010];
int top=-1;
int main()
{
    int n,e,v;
    scanf("%d%d%d",&n,&e,&v);
    for(int i=1;i<=e;i++)adj[i]=NULL;
    for(int k=1;k<=e;k++)
    {
        int i,j,w;
        scanf("%d%d%d",&i,&j,&w);
        s=&a[++top];s->vex=j;s->next=adj[i];adj[i]=s;s->wgt=w;
    }
    for(int i=1;i<=n;i++)
    {
        d[i].no=i;d[i].dis=INF;
        vis[i]=false;
    }
    d[v].dis=0;q.push(d[v]);
    while(!q.empty())
    {
        node cd=q.top();q.pop();
        int u=cd.no;
        if(vis[u])continue;
        vis[u]=true;
        enode *p=adj[u];
        while(p!=NULL)
        {
            int vv=p->vex;
            if(d[vv].dis>d[u].dis+p->wgt&&!vis[vv])
            {
                d[vv].dis=d[u].dis+p->wgt;q.push(d[vv]);
            }
            p=p->next;
        }
    }
    for(int i=1;i<=n;i++)
    cout<<d[i].dis<<' ';
    return 0;
}